import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Others {
    public static int hammingWeight(int n) {
        int counter = 0;
        while (n != 0)
        {
            if (n % 2 != 0) {
                counter++;
            }
            n = n >>> 1;
        }
        return counter;
    }

    public static int hammingDistance(int x, int y) {
        int result=0;
        int mod1,mod2;
        while (x!=0||y!=0){
            mod1=x%2;
            mod2=y%2;
            x=x/2;
            y=y/2;
            if(mod1!=mod2)result++;
        }
        return result;
    }

    public static int reverseBits(int n) {
        StringBuffer strb=new StringBuffer();
        while (n != 0)
        {

            strb.append(n%2);
            n = n >>> 1;
        }
        if(strb.toString().equals(""))return 0;
        return Integer.valueOf(strb.toString());
    }

    public static boolean isValid(String s) {
        int len=s.length();
        if(len%2!=0)return false;
        StringBuffer str=new StringBuffer(s);
        Stack<Character> stack=new Stack<>();
        try {
            for (int i=0;i<len;i++){
                char c=s.charAt(i);
                char c2;
                switch (c) {
                    case '(':
                        stack.push(c);
                        break;
                    case '{':
                        stack.push(c);
                        break;
                    case '[':
                        stack.push(c);
                        break;
                    case ')':
                        c2=stack.pop();
                        if(c2!='('){
                            return false;
                        }
                        break;
                    case '}':
                        c2=stack.pop();
                        if(c2!='{'){
                            return false;
                        }
                        break;
                    case ']':
                        c2=stack.pop();
                        if(c2!='['){
                            return false;
                        }
                        break;
                }
            }
            if(!stack.empty()){
                return false;
            }
            return true;
        }catch (Exception e){
            return false;
        }

    }

    public List<List<Integer>> generate(int numRows) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> result=new ArrayList<>();
        if(numRows==0){
            return result;
        }
        list.add(1);
        result.add(list);
        for (int i=1;i<numRows;i++){
            List<Integer> pre=result.get(i-1);
            list=new ArrayList<>();
            list.add(1);
            for (int j=0;j<i-1;j++){
                list.add(pre.get(j)+pre.get(j+1));
            }
            list.add(1);
            result.add(list);
        }
        return result;
    }
    public int missingNumber(int[] nums) {
        int len=nums.length;
        int []data=new int[len+1];
        for (int i=0;i<len;i++){
            data[nums[i]]++;
        }
        for(int i=0;i<len+1;i++){
            if(data[i]==0)return i;
        }
        return -1;

    }
}
